home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / storage / ipc / shmqueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  5.9 KB  |  259 lines
  1. /*
  2.  * shmqueue.c -- shared memory linked lists
  3.  *
  4.  * Identification:
  5.  *    $Header: /private/postgres/src/storage/ipc/RCS/shmqueue.c,v 1.3 1992/04/13 19:00:55 mer Exp $
  6.  *
  7.  * Package for managing doubly-linked lists in shared memory.
  8.  * The only tricky thing is that SHM_QUEUE will usually be a field 
  9.  * in a larger record.  SHMQueueGetFirst has to return a pointer
  10.  * to the record itself instead of a pointer to the SHMQueue field
  11.  * of the record.  It takes an extra pointer and does some extra
  12.  * pointer arithmetic to do this correctly.
  13.  *
  14.  * NOTE: These are set up so they can be turned into macros some day.
  15.  */
  16. #include "tmp/postgres.h"
  17. #include "storage/shmem.h"
  18. #include "utils/log.h"
  19.  
  20. /*
  21.  * ShmemQueueInit -- make the head of a new queue point
  22.  *     to itself
  23.  */
  24. SHMQueueInit(queue)
  25. SHM_QUEUE    *queue;
  26. {
  27.   Assert(SHM_PTR_VALID(queue));
  28.   (queue)->prev = (queue)->next = MAKE_OFFSET(queue);
  29. }
  30.  
  31. /*
  32.  * SHMQueueIsDetached -- TRUE if element is not currently
  33.  *    in a queue.
  34.  */
  35. SHMQueueIsDetached(queue)
  36. SHM_QUEUE     *queue;
  37. {
  38.   Assert(SHM_PTR_VALID(queue));
  39.   return ((queue)->prev == INVALID_OFFSET);
  40. }
  41.  
  42. /*
  43.  * SHMQueueElemInit -- clear an element's links
  44.  */
  45. SHMQueueElemInit(queue)
  46. SHM_QUEUE     *queue;
  47. {
  48.   Assert(SHM_PTR_VALID(queue));
  49.   (queue)->prev = (queue)->next = INVALID_OFFSET;
  50. }
  51.  
  52. /*
  53.  * SHMQueueDelete -- remove an element from the queue and
  54.  *     close the links
  55.  */
  56. SHMQueueDelete(queue)
  57. SHM_QUEUE    *queue;
  58. {
  59.   SHM_QUEUE *nextElem = (SHM_QUEUE *) MAKE_PTR((queue)->next);
  60.   SHM_QUEUE *prevElem = (SHM_QUEUE *) MAKE_PTR((queue)->prev);
  61.  
  62. /*
  63.   dumpQ(queue);
  64. */
  65.  
  66.   Assert(SHM_PTR_VALID(queue));
  67.   Assert(SHM_PTR_VALID(nextElem));
  68.   Assert(SHM_PTR_VALID(prevElem));
  69.   prevElem->next =  (queue)->next;
  70.   nextElem->prev =  (queue)->prev;
  71.  
  72. /*
  73.   dumpQ((SHM_QUEUE *)MAKE_PTR(queue->prev));
  74. */
  75.  
  76. }
  77.  
  78. dumpQ(q)
  79. SHM_QUEUE    *q;
  80. {
  81.     char elem[16];
  82.     char buf[512];
  83.     SHM_QUEUE    *start = q;
  84.     int count = 0;
  85.  
  86.     sprintf(buf, "q prevs: %x", MAKE_OFFSET(q));
  87.     q = (SHM_QUEUE *)MAKE_PTR(q->prev);
  88.     while (q != start)
  89.     {
  90.     sprintf(elem, "--->%x", MAKE_OFFSET(q));
  91.     strcat(buf, elem);
  92.     q = (SHM_QUEUE *)MAKE_PTR(q->prev);
  93.     if (q->prev == MAKE_OFFSET(q))
  94.         break;
  95.     if (count++ > 40)
  96.     {
  97.         strcat(buf, "BAD PREV QUEUE!!");
  98.         break;
  99.     }
  100.     }
  101.     sprintf(elem, "--->%x", MAKE_OFFSET(q));
  102.     strcat(buf, elem);
  103.     elog(DEBUG, buf);
  104.  
  105.     sprintf(buf, "q nexts: %x", MAKE_OFFSET(q));
  106.     count = 0;
  107.     q = (SHM_QUEUE *)MAKE_PTR(q->next);
  108.     while (q != start)
  109.     {
  110.     sprintf(elem, "--->%x", MAKE_OFFSET(q));
  111.     strcat(buf, elem);
  112.     q = (SHM_QUEUE *)MAKE_PTR(q->next);
  113.     if (q->next == MAKE_OFFSET(q))
  114.         break;
  115.     if (count++ > 10)
  116.     {
  117.         strcat(buf, "BAD NEXT QUEUE!!");
  118.         break;
  119.     }
  120.     }
  121.     sprintf(elem, "--->%x", MAKE_OFFSET(q));
  122.     strcat(buf, elem);
  123.     elog(DEBUG, buf);
  124. }
  125.  
  126. /*
  127.  * SHMQueueInsertHD -- put elem in queue between the queue head
  128.  *    and its "prev" element.
  129.  */
  130. SHMQueueInsertHD(queue,elem)
  131. SHM_QUEUE *queue,*elem;
  132. {
  133.   SHM_QUEUE *prevPtr = (SHM_QUEUE *) MAKE_PTR((queue)->prev);
  134.   SHMEM_OFFSET    elemOffset = MAKE_OFFSET(elem);
  135.  
  136.   Assert(SHM_PTR_VALID(queue));
  137.   Assert(SHM_PTR_VALID(elem));
  138.  
  139.   (elem)->next = prevPtr->next;
  140.   (elem)->prev = queue->prev;
  141.   (queue)->prev = elemOffset;
  142.   prevPtr->next = elemOffset;
  143. }
  144.  
  145. SHMQueueInsertTL(queue,elem)
  146. SHM_QUEUE *queue,*elem;
  147. {
  148.   SHM_QUEUE *nextPtr = (SHM_QUEUE *) MAKE_PTR((queue)->next);
  149.   SHMEM_OFFSET    elemOffset = MAKE_OFFSET(elem);
  150.  
  151.   Assert(SHM_PTR_VALID(queue));
  152.   Assert(SHM_PTR_VALID(elem));
  153.  
  154. /*
  155.   dumpQ(queue);
  156. */
  157.  
  158.   (elem)->prev = nextPtr->prev;
  159.   (elem)->next = queue->next;
  160.   (queue)->next = elemOffset;
  161.   nextPtr->prev = elemOffset;
  162.  
  163. /*
  164.   dumpQ(queue);
  165. */
  166. }
  167.  
  168. /*
  169.  * SHMQueueFirst -- Get the first element from a queue
  170.  *
  171.  * First element is queue->next.  If SHMQueue is part of
  172.  * a larger structure, we want to return a pointer to the
  173.  * whole structure rather than a pointer to its SHMQueue field.
  174.  * I.E. struct {
  175.  *    int         stuff;
  176.  *    SHMQueue     elem;
  177.  * } ELEMType; 
  178.  * when this element is in a queue (queue->next) is struct.elem.
  179.  * nextQueue allows us to calculate the offset of the SHMQueue
  180.  * field in the structure.
  181.  *
  182.  * call to SHMQueueFirst should take these parameters:
  183.  *
  184.  *   &(queueHead),&firstElem,&(firstElem->next)
  185.  *
  186.  * Note that firstElem may well be uninitialized.  if firstElem
  187.  * is initially K, &(firstElem->next) will be K+ the offset to
  188.  * next.
  189.  */
  190. SHMQueueFirst(queue,nextPtrPtr,nextQueue)
  191. SHM_QUEUE    *queue;
  192. Addr     *nextPtrPtr;
  193. SHM_QUEUE    *nextQueue;
  194. {
  195.   SHM_QUEUE *elemPtr = (SHM_QUEUE *) MAKE_PTR((queue)->next);
  196.  
  197.   Assert(SHM_PTR_VALID(queue));
  198.   *nextPtrPtr = (Addr) (((unsigned) *nextPtrPtr) +
  199.     ((unsigned) elemPtr) - ((unsigned) nextQueue)); 
  200.  
  201.   /*
  202.   nextPtrPtr a ptr to a structure linked in the queue
  203.   nextQueue is the SHMQueue field of the structure
  204.   *nextPtrPtr - nextQueue is 0 minus the offset of the queue 
  205.       field n the record 
  206.   elemPtr + (*nextPtrPtr - nexQueue) is the start of the
  207.       structure containing elemPtr.
  208.   */
  209. }
  210.  
  211. /*
  212.  * SHMQueueDoLRU -- move elem to the front of the list
  213.  */
  214. SHMQueueDoLRU(queue,elem)
  215. SHM_QUEUE    *queue;
  216. SHM_QUEUE    *elem;
  217. {
  218.   Assert(SHM_PTR_VALID(queue));
  219.  
  220.   /* do not LRU if the element is currently detached from the queue */
  221.   if ((elem)->prev == INVALID_OFFSET)
  222.     return;
  223.  
  224.   SHMQueueDelete(elem);
  225.   SHMQueueInsertTL(queue,elem);
  226. }
  227.  
  228.  
  229. SHMQueueCheck(queue)
  230. SHM_QUEUE    *queue;
  231. {
  232.   SHM_QUEUE *nextElem = (SHM_QUEUE *) MAKE_PTR((queue)->next);
  233.   SHM_QUEUE *prevElem = (SHM_QUEUE *) MAKE_PTR((queue)->prev);
  234.  
  235. /*
  236.   printf("curr: %x next %x prev %x: prev.next %x next.prev %x\n",
  237.      MAKE_OFFSET(queue),queue->next,queue->prev,
  238.      nextElem->prev,prevElem->next);
  239. */
  240.   Assert(nextElem->prev == MAKE_OFFSET(queue));
  241.   Assert(prevElem->next == MAKE_OFFSET(queue));
  242. }
  243.  
  244. /*
  245.  * SHMQueueEmpty -- TRUE if queue head is only element, FALSE otherwise
  246.  */
  247. SHMQueueEmpty(queue)
  248. SHM_QUEUE       *queue;
  249. {
  250.   Assert(SHM_PTR_VALID(queue));
  251.  
  252.   if (queue->prev == MAKE_OFFSET(queue)) 
  253.   {
  254.     Assert(queue->next = MAKE_OFFSET(queue));
  255.     return(TRUE);
  256.   }
  257.   return(FALSE);
  258. }
  259.